In the area of digital printing, representation of the intensity of a color on paper, i.e., the gray level, has been the object of a wide variety of algorithms published in the last decade. Digital printers are defined as those printers that are capable of making a mark, usually in the form of a dot, of a given, uniform size and at a specified resolution in marks per unit length, typically dots per inch (dpi), on paper. To use such a digital printer to give the impression of color intensity, it has been common to place the marks, or dots, on the paper according to a variety of geometrical patterns such that a group of dots and dotless blank spots when seen by the eye gives a rendition of an intermediate color tone between the color of the initial paper stock, usually white, and total ink coverage, or solid density. In the ensuing paragraphs, discussions will be made in terms of white paper stock; it is understood that white paper stock is used as an illustration and not as a limitation of any invention.
An obvious problem arises when the resolution of the dot matrix on the paper is not very high, for example, 100 dpi or less, and the geometrical patterns being used become particularly visible to the eye. In this case the viewer is distracted from the image being represented by the image artifacts of geometrical patterns themselves and perceives the impression of an image of poor quality. The obvious solution to this problem is to work at very high resolutions, for example, 300 dpi or greater, so that those artifacts are less perceived and their negative effects become less glaring.
In 1976, Robert W. Floyd and Louis Steinberg published a paper in the Proceedings of the S.I.D., Vol. 17/2, entitled "An Adaptive Algorithm for Spatial Greyscale". In it they described an algorithm which they called "Error Diffusion" (ED). This algorithm provides a method for a gray scale with bilevel devices, that is, dot or no dot. According to this prior art scheme, gray level data representing a continuous tone image is subjected to a thresholding process whereby gray levels above a chosen threshold, for example, 50%, are assigned a dot to be printed and those below are not assigned a dot. The coarseness of this method is compensated for by keeping track of the intensity error due to this process and propagating this error in specified amounts to adjacent picture elements, or "pixels", to weight the pixels in the thresholding process. This approach results in a more accurate representation of a grey tone over a small area encompassing several dots. Hence, perception of the image artifacts is diminished, and a better quality gray scale image is generated. Furthermore, the ED algorithm retains good edge quality in generated images to minimize the inherent "fuzziness" of a bilevel generated image.
It has been observed by subsequent investigators that the ED approach, even at resolutions of 300 dpi, still suffers severe limitations in producing quality images. See, for example, C. Billotet-Hoffman and O. Bryngdahl, Proceedings of S.I.D., Vol. 24/3, p. 253, "On the Error Diffusion Technique for Electronic Halftoning"; Yigdl Gur and F. X. D. O'Donnell, TAGA Proceedings, 1985, p. 603, "Half-toning Using Ink-Jet: Part I. Algorithm of Discretization"; and Yigal Gur and F. X. D. O'Donnell, TAGA Proceedings, 1985, p. 611, "Half-toning Using Ink Jet: Part 2. Tailoring Algorithm to a Printer", the contents of all of which are incorporated herein by reference. Specifically, with the ED approach in producing gray scale images, the dots of a binary printer are of greater diameter than the separation of the addressable points; therefore, they can overlap. This overlapping then produces a nonlinear response to the representation of the grey tone discretization. In addition, the thresholding process also introduces undesirable patterns or textures that are visible to the eye when certain grey levels are printed. Gur and O'Donnell describe a means of randomizing the threshold to solve the latter problem. This solution, however, requires more complex and time consuming algorithms.